import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//四数之和
//测试链接 https://leetcode.cn/problems/4sum/
public class FourSum {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();  //保存结果
        int n = nums.length-1; //数组最后一个下标

        for(int i = 0; i <= n;){
            for(int j = i+1; j <= n; ){
                long num = (long)target - (long)nums[i] - (long)nums[j];
                int left = j + 1, right = n;

                while(left < right){
                    int l = nums[left], r = nums[right];

                    if(l + r > num){
                        right--;
                    }else if(l + r < num){
                        left++;
                    }else{
                        ans.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j],nums[left],nums[right])));

                        left++; right--;
                        //去重
                        while(left < right && nums[left] == l) left++;
                        while(left < right && nums[right] == r)right--;
                    }
                }
                j++;
                //去重
                while(j <= n &&  nums[j] == nums[j-1] ){
                    j++;
                }
            }
            i++;
            //去重
            while(i <= n &&  nums[i] == nums[i-1] ){
                i++;
            }
        }

        return ans;
    }
}
